#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;

template <class Compareable>
class BinarySearchTree;

template <class Compareable>
class BinaryNode
{
	Compareable element;
	BinaryNode *left;
	BinaryNode *right;

	BinaryNode(const Compareable & theElement, BinaryNode *lt,
											   BinaryNode *rt)
	: element(theElement), left(lt), right(rg) { }
	friend class BinarySearchTree<Compareable>;
};

template <class Compareable>
class BinarySearchTree
{
  public:
  	explicit BinarySearchTree(const Compareable &notFound);
	BinarySearchTree(const BinarySearchTree &rhs);
	~BinarySearchTree();

	const Compareable & findMin() const;
	const Compareable & findMx() const;
	const Compareable & find(const Compareable &x) const;
	bool isEmpty() const;
	void printTree() const;

	void makeEmpty();
	void insert(const Compareable &x);
	void remove(const Compareable &x);

	const BinarySearchTree & operator=(const BinarySearchTree &rhs);

  private:
  	BinaryNode<Compareable> *root;
	const Compareable ITEM_NOT_FOUND;

	const Compareable & elementAt(BinaryNode<Compareable> *t) const;

	void insert(const Compareable &x, BinaryNode<Compareable> * &t) const;
	void remove(const Compareable &x, BinaryNode<Compareable> * &t) const;
	BinaryNode<Compareable> * findMin(BinaryNode<Compareable> *t) const;
	BinaryNode<Compareable> * findMax(BinaryNode<Compareable> *t) const;
	BinaryNode<Compareable> * find(const Compareable &x, 
					               BinaryNode<Compareable> *t) const;
	void makeEmpty(BinaryNode<Compareable> * &t) const;
	void printTree(BinaryNode<Compareable> *t) const;
	BinaryNode<Compareable> *clone(BinaryNode<Compareable> *t) const;
};
#endif
